package lanQiaoBei.tree;

import java.util.LinkedList;
import java.util.Stack;

public class TestTreeProblem {
    private static int val=Integer.MIN_VALUE;
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node1.setLeft(node7);
        node1.setRight(node2);
        node3.setLeft(node1);
        node3.setRight(node4);
//        node4.setRight(node5);
        node4.setLeft(node6);
        System.out.println(isBSTByRec(node3));
        System.out.println(isBSTByStack(node3));
        System.out.println(isCBT(node3));
        System.out.println(isFBT(node3));
    }
    //实现判断一棵树是否为满二叉树
    public static boolean isFBT(TreeNode root){
          if(root==null)return true;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addFirst(root);
        while (!queue.isEmpty()){
            TreeNode removeLast = queue.removeLast();
            TreeNode left = removeLast.getLeft();
            TreeNode right = removeLast.getRight();
            if(left==null&&right==null){

            }else if(left==null||right==null)return false;
            if(left!=null){
                queue.addFirst(left);
            }
            if(right!=null){
                queue.addFirst(right);
            }
        }
        return true;
    }
    //实现判断一棵树是否为完全二叉树
    public static boolean isCBT(TreeNode root){
        if(root==null)return true;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addFirst(root);
        boolean isNoAll=false;
        while (!queue.isEmpty()){
            TreeNode removeLast = queue.removeLast();
            TreeNode left = removeLast.getLeft();
            TreeNode right = removeLast.getRight();
            if(right!=null&&left==null)return false;
            if(isNoAll&&(left!=null||right!=null))return false;
            if(left!=null){
                queue.addFirst(left);
            }
            if(right!=null){
                queue.addFirst(right);
            }
            if(left==null||right==null)isNoAll=true;
        }
        return true;
    }
    //非递归实现是否是搜索二叉树
    public static boolean isBSTByStack(TreeNode root){
           if(root==null){
               return true;
           }
           int val=Integer.MIN_VALUE;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty()||root!=null){
              if(root!=null){
                  stack.push(root);
                  root=root.getLeft();
              }else {
                  TreeNode pop = stack.pop();
                  if(pop.getVal()>val){
                      val=pop.getVal();
                  }else return false;
                  root=pop.getRight();
              }
        }
        return true;
    }
//    递归实现是否是搜索二叉树 中序遍历二叉树看是否是升序的
    public static boolean isBSTByRec(TreeNode root){
           if(root==null){
               return true;
           }
        boolean isL = isBSTByRec(root.getLeft());
           if(isL&&root.getVal()>val){
               val=root.getVal();
           }else return false;
        return isBSTByRec(root.getRight());
    }
}
